EVENTO
Algoritmos Quânticos para o Problema do Isomorfismo de Grafos
Tipo de evento: Defesa de Dissertação de Mestrado
O problema do isomorfismo de grafos possui aplicações em diversas áreas da ciência. Tal problema não possui uma solução eficiente para o seu caso geral. No presente trabalho, apresentamos os conceitos básicos em teoria de grupos, teoria dos grafos e mecânica quântica. Apresentamos o problema do subgrupo oculto e uma conhecida redução polinomial do problema do isomorfismo de grafos no seu caso geral para o problema do subgrupo oculto sobre o grupo simétrico. Utilizamos um método que reduz o problema do isomorfismo de grafos para o problema de interseção de grupos. Este método utiliza resultados da computação quântica e da teoria dos grupos solúveis, nos permitindo obter uma solução eficiente através de um algoritmo quântico para o problema do isomorfismo de grafos para uma classe particular de grafos.
Data Início: 14/03/2008 Hora: 10:00 Data Fim: 14/03/2008 Hora: 12:00
Local: LNCC - Laboratório Nacional de Computação Ciêntifica - Auditorio A
Aluno: Edinelço Dalcumune - LNCC - LNCC
Orientador: Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Participante Banca Examinadora: Celina Miraglia Herrera de Figueiredo - COPPE - UFRJ Gilson Antônio Giraldi - Laboratório Nacional de Computação Científica - LNCC Renato Portugal - Laboratório Nacional de Computação Científica - LNCC
Suplente Banca Examinadora: Carlile Campos Lavor - Universidade Estadual de Campinas - IMECC/UNICAMP Paulo César Marques Vieira - Laboratório Nacional de Computação Científica - LNCC
